# 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
#  每行的元素从左到右升序排列。
#  每列的元素从上到下升序排列。
#
#  示例 1：
# 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
# 输出：true
#
#  示例 2：
# 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
# 输出：false
from typing import List


class Solution:
    def searchMatrix2(self, matrix: List[List[int]], target: int) -> bool:
        """
        解法二
        从矩阵的右上开始尝试寻找
        如果 matrix[i][j] == target 返回true
        如果 matrix[i][j] > target j--
        否则 i++
        退出循环则返回 false
        :param matrix:
        :param target:
        :return:
        """
        rows = len(matrix)
        columns = len(matrix[0])
        i, j = 0, columns - 1
        while i < rows and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:
                i += 1
        return False

    def searchMatrix1(self, matrix: List[List[int]], target: int) -> bool:
        """
        解法一:分治
        由于矩阵行列都是递增的，
        遍历矩阵的对角线上的元素
        若该元素小于目标 target元素，则它的左上所有元素都小于target
        若该元素大于目标 target元素，则它的右下所有元素都大于target
        即不用再去左上和右下的区域
        只需要在右上和左下进行递归查找即可
        :param matrix:
        :param target:
        :return:
        """
        def search(startRow: int, startCol: int, endRow: int, endCol: int) -> bool:
            if startRow > endRow or startCol > endCol:  # 越界直接返回False
                return False
            # target 小于矩阵的最小值 或者大于矩阵的最大值，那么肯定不在矩阵中
            if matrix[startRow][startCol] > target or matrix[endRow][endCol] < target:
                return False
            diagonaLen = min(endRow - startRow + 1, endCol - startCol + 1)  # 求矩阵的对角线长
            for i in range(diagonaLen):  # 沿矩阵的对角线查找(矩阵的行列可能不等)
                if matrix[startRow + i][startCol + i] == target:
                    return True
                if i == diagonaLen - 1\
                        or matrix[startRow + i + 1][startCol + i + 1] > target:  # 如果小于对角线的当前元素的下一个元素，说明知道了划分区域的位置
                    return (search(startRow, startCol + i + 1, startRow + i, endCol)  # 尝试在右上区域寻找
                            or search(startRow + i + 1, startCol, endRow, startCol + i))  # 尝试在左下区域寻找
            return False
        return search(0, 0, len(matrix) - 1, len(matrix[0]) - 1)

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        return self.searchMatrix2(matrix, target)


if __name__ == "__main__":
    matrix = [[1, 4, 7, 11, 15],
              [2, 5, 8, 12, 19],
              [3, 6, 9, 16, 22],
              [10, 13, 14, 17, 24],
              [18, 21, 23, 26, 30]]
    target = 5
    print(Solution().searchMatrix(matrix, target))
